In order to route from one address to another in an interconnecting network with numerous users, data related to various transmission paths is generally stored together to form a routing table, which is queried during routing.
Classless inter-domain routing (CIDR) is a commonly used routing table structure. When a routing table with the CIDR structure is used, an Internet protocol (IP) network is represented by a prefix, which is generally formed by an IP address of the IP network and a mask indicating the significant bits of the IP address. For example, “111*” indicates an IP address of “111” with three significant bits. The routing table is generally stored in a form of a Multi-Bit Tire. Routing table items of 2n (n is an integer) sub-networks adjacent to each other in the address space and sharing the same route are combined into one path, and stored in the routing table as one entry, so that the routing table is searched according to the path.
Here, the storage method is described by way of citing an example. It is assumed that there are nine prefixes, namely, “P1”, “P2”, “P3”, “P4”, “P5”, “P6”, “P7”, “P8”, and “P9”, and the relations between prefix labels and prefix values are as shown in Table 1.
TABLE 1Relation between Prefix Labels and Prefix ValuesPrefix LabelPrefix ValueP1*P21*P300*P4101*P5111*P61000*P711101*P8111001*P91000011*
A basic binary tree search is performed at a rate of checking one bit in each step. If a corresponding maximum address prefix is M, the depth of the tree is M. If K bits are checked each time, the depth of the tree can be reduced to M/K, and accordingly, the number of matching entries contained in each internal node of the tree is increased to 2K. Such a tree is called a 2K branched tree, which has a maximum layer number of M/K. The number of bits checked by the table searched algorithm at each node is K, which is also referred to as a step length of the tree.
If the step length of the Multi-Bit Tire is 3, each node in the tree contains 23, i.e. 8, entries, and the structure thereof is as shown in Table 2.
TABLE 2Node Structure with Step Length of 3Matching EntryNext-level Node Pointer000——001——010——011——100——101——110——111——
A prefix matching entry refers to a prefix that matches with the entry. For example, “P1” corresponds to a value of “*”, indicating that “P1” can match with any entry; and if the node is a root node, and an initial record is null, “000” to “111” are all matching entries of “P1”. “P2 ” corresponds to a value of “1*”, indicating that an IP address of “P2” is “1” with one significant bit, so that any entry starting with “1” can match with “P2”; and if the node is a root node, “100” to “111” are all matching entries of “P2”. At this time, if “P1”has been stored, “100” to “111” are overwritten by “P2” when “P2” is stored. The storage methods for other prefixes with no more than three significant bits, namely, “P3”, “P4”, and “P5”, may be deduced similarly. Particularly, “000” and “001” are matching entries of “P3”; “101” is a matching entry of “P4”; and “111” is a matching entry of“P5”. A node structure with “P1”, “P2”, “P3”, “P4”, and “P5” being stored is as shown in Table 3.
TABLE 3Node Structure with “P1”, “P2”, “P3”, “P4”, and “P5” Being StoredMatching EntryNext-level Node Pointer000P3—001P3—010P1—011P1—100P2—101P4—110P2—111P5—
In the column of “Next-level Node Pointer (Ptr)” in Tables 2 and 3, each pointer pointing to a next-level node is stored. That is because a next-level node needs to be established when the significant bits of a prefix exceed the step length of the node. According to such a pointer, the next-level node may be found during query.
Taking “P6”, “P7”, “P8”, and “P9” as examples, “P6” corresponds to a value of “1000*”, indicating that “P6” has four significant bits and no matching entry can be found in the root node with the step length of 3. Therefore, a next-level node needs to be established when “P6” is stored. As “100” in the root node matches with the first three bits of “P6”, a newly established next-level node pointer is stored in the column of “Next-level Node Pointer” corresponding to “100”. In the newly established next-level node, all entries starting with “0” can match with “P6”. A node structure with “P6” being stored is as shown in Table 4.
TABLE 4Node Structure with “P6” Being StoredMatching EntryNext-level Node Pointer000P6—001P6—010P6—011P6—100——101——110——111——
As “P7” corresponds to a value of “11101*” and “P8” corresponds to a value of “111001*”, the first three bits thereof are the same, i.e. “111”. Therefore, a next-level node may be established for “P7” and “P8”. Particularly, a newly established next-level node pointer is stored in the column of “Next-level Node Pointer” corresponding to the root node of “111”. Thus, in the newly established next-level node, “010” and “011” starting with “01” both match with “P7 ”, and “001” matches with “P8”. A node structure with “P7” and “P8” being stored is as shown in Table 5.
TABLE 5Node Structure with “P7” and “P8” Being StoredMatching EntryNext-level Node Pointer000——001P8—010P7—011P7—100——101——110——111——
As “P9” corresponds to a value of “1000011*” with seven significant bits, which are over twice as much as the step length “3” of the node, a further new level node needs to be established based on the next-level node of the root node. During the establishment process, it is determined whether the existing nodes have an entry that matches with the first six bits of “P9” or not. If yes, a newly established node pointer is filled into the column of “Next-level Node Pointer” corresponding to this entry; otherwise, a newly established node pointer is filled into the column of “Next-level Node Pointer” corresponding to an entry in the root node that matches with the first three bits of “P9”. In this example, the node “001” as shown in Table 4 with “P6” already being stored matches with the first six bits of “P9”, so that a newly established node pointer is filled into the column of “Next-level Node Pointer” corresponding to this entry, and any newly established entry starting with “1” matches with “P9”. A node structure with “P9” being stored is as shown in Table 6.
TABLE 6Node Structure with “P9” Being StoredMatching EntryNext-level Node Pointer000——001——010——011——100P9—101P9—110P9—111P9—
“P1”, “P2”, “P3”, “P4”, “P5”, “P6”, “P7”, “P8 ”, and “P9” are all stored in the Multi-Bit Tire with the step length of 3. FIG. 1 shows a complete structure of the Multi-Bit Tire.
The Multi-Bit Tire includes a root node equivalent to the nodes shown in Table 3, a node 1 equivalent to the nodes shown in Table 4, a node 2 equivalent to the nodes shown in Table 5, and a node 3 equivalent to the nodes shown in Table 6.
During the research and implementation process of the related art, the inventor(s) found that the prior art has the following problem.
Each node needs to apply for a fixed-size storage space, but most entries of the nodes do not have a corresponding next-level node, that is, most of the Ptr entries are null. For example, in FIG. 1, totally 29 Ptr entries are null, which wastes a lot of memory resources. In most cases, the memory resources are very limited. In practice, as a routing table may have up to hundreds or thousands of nodes or even more, more memory resources may be wasted.